|
The Stream X-machine (SXM) is a model of computation introduced by Gilbert Laycock in his 1993 PhD thesis, ''The Theory and Practice of Specification Based Software Testing''.〔 name="Lay93">Gilbert Laycock (1993) ''The Theory and Practice of Specification Based Software Testing''. PhD Thesis, University of Sheffield, Dept of Computer Science. (Abstract )〕 Based on Samuel Eilenberg's X-machine, an extended finite state machine for processing data of the type ''X'',〔Samuel Eilenberg (1974) ''Automata, Languages and Machines, Vol. A''. London: Academic Press.〕 the Stream X-Machine is a kind of X-machine for processing a memory data type ''Mem'' with associated input and output streams ''In'' * and ''Out'' *, that is, where ''X'' = ''Out'' * × ''Mem'' × ''In'' *. The transitions of a Stream X-Machine are labelled by functions of the form φ: ''Mem'' × ''In'' → ''Out'' × ''Mem'', that is, which compute an output value and update the memory, from the current memory and an input value. Although the general X-machine had been identified in the 1980s as a potentially useful formal model for specifying software systems,〔 M. Holcombe (1988) 'X-machines as a basis for dynamic system specification'. ''Software Engineering Journal'' 3 ''(2)'', pp. 69-76.〕 it was not until the emergence of the Stream X-Machine that this idea could be fully exploited. Florentin Ipate and Mike Holcombe went on to develop a theory of ''complete'' functional testing,〔 name="HolIp98">Mike Holcombe and Florentin Ipate (1998) ''Correct systems - building a business process solution''. Applied Computing Series. Berlin: Springer-Verlag.〕 in which complex software systems with hundreds of thousands of states and millions of transitions could be decomposed into separate SXMs that could be tested exhaustively, with a guaranteed proof of correct integration.〔F. Ipate and W. M. L. Holcombe (1997) 'An integration testing method which is proved to find all faults'. ''Int. J. Comp. Math.'', 63, pp. 159-178.〕 Because of the intuitive interpretation of Stream X-Machines as "processing agents with inputs and outputs", they have attracted increasing interest, because of their utility in modelling real-world phenomena. The SXM model has important applications in fields as diverse as computational biology, software testing and agent-based computational economics. == The Stream X-Machine == A Stream X-Machine (SXM) is an extended finite state machine with auxiliary memory, inputs and outputs. It is a variant of the general X-machine, in which the fundamental data type ''X'' = ''Out'' * × ''Mem'' × ''In'' *, that is, a tuple consisting of an output stream, the memory and an input stream. A SXM separates the ''control flow'' of a system from the ''processing'' carried out by the system. The control is modelled by a finite state machine (known as the ''associated automaton'') whose transitions are labelled with processing functions chosen from a set Φ (known as the ''type'' of the machine), which act upon the fundamental data type. Each processing function in Φ is a partial function, and can be considered to have the type φ: ''Mem'' × ''In'' → ''Out'' × ''Mem'', where ''Mem'' is the memory type, and ''In'' and ''Out'' are respectively the input and output types. In any given state, a transition is ''enabled'' if the domain of the associated function φi includes the next input value and the current memory state. If (at most) one transition is enabled in a given state, the machine is ''deterministic''. Crossing a transition is equivalent to applying the associated function φi, which consumes one input, possibly modifies the memory and produces one output. Each recognised path through the machine therefore generates a list φ1 ... φn of functions, and the SXM composes these functions together to generate a relation on the fundamental data type |φ1 ... φn|: ''X'' → ''X''. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Stream X-Machine」の詳細全文を読む スポンサード リンク
|